package search.backtracking;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Classname : LetterCombinationsOfAPhoneNumber
 * @Description : 17. 电话号码的字母组合
 * https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
 * @Author : chentianyu
 * @Date 2023/3/3 23:28
 */


public class LetterCombinationsOfAPhoneNumber {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        int n = digits.length();
        if (digits == null || n == 0) return ans;
        // 获取数字到字母的映射
        Map<Integer, String> map = getMap();
        // 根据给出数字字符串获取可用于组合的字母矩阵
        List<String> mat = new ArrayList<>();
        for (char c : digits.toCharArray()) mat.add(map.get(c - '0'));
        // 回溯法进行字母组合
        backTacking(mat, n, 0, new char[n], ans);
        return ans;
    }

    private void backTacking(List<String> mat, int k, int p, char[] comb, List<String> ans) {
        if (p == k) {
            StringBuilder str = new StringBuilder();
            for (char s : comb) str.append(s);
            ans.add(str.toString());
            return;
        }

        for (char c : mat.get(p).toCharArray()) {
            comb[p] = c;
            backTacking(mat, k, p + 1, comb, ans);
        }
    }

    private Map<Integer, String> getMap() {
        Map<Integer, String> map = new HashMap<>();
        map.put(2, "abc");
        map.put(3, "def");
        map.put(4, "ghi");
        map.put(5, "jkl");
        map.put(6, "mno");
        map.put(7, "pqrs");
        map.put(8, "tuv");
        map.put(9, "wxyz");
        return map;
    }
}
